// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
// 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
// strs[i] 仅由 '0' 和 '1' 组成

// 输入：strs = ["10", "0", "1"], m = 1, n = 1
// 输出：2
// 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

int findMaxForm(char ** strs, int strsSize, int m, int n){
    // 最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
    int dp[m+1][n+1];
    //初始化
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = 0;

    int cnt, zero_num, one_num;
    for (int i = 0; i < strsSize; i++) {    //0-1背包，物品有两个维度
        // 统计字符串中0，1个数
        cnt = 0;
        zero_num = 0, one_num = 0;
        while (strs[i][cnt] != '\0') {
            if (strs[i][cnt] == '0') zero_num++;
            else one_num++;
            cnt++;
        }

        for (int j = m; j >= zero_num; j--) {
            for (int k = n; k >= one_num; k--) {
                dp[j][k] = fmax(dp[j][k], dp[j - zero_num][k - one_num] + 1);
            }
        }
    }
    return dp[m][n];
}